// https://leetcode-cn.com/problems/permutation-in-string/
// 567. 字符串的排列
/*
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
*/
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (t, s) {
  // 需要的
  let need = {}
  // 窗口中的字符
  let win = {}
  for (let a of t) {
    // 统计需要的字符
    need[a] = (need[a] || 0) + 1
  }
  // 左右指针
  let left = 0
  let right = 0
  let valid = 0
  while (right < s.length) {
    // 即将移入窗口的字符
    let rc = s[right]
    // 右移窗口
    right++
    if (need[rc]) {
      // 当前字符在需要的字符中，则更新当前窗口统计
      win[rc] = (win[rc] || 0) + 1
      if (win[rc] == need[rc]) {
        // 当前窗口和需要的字符匹配时，验证数量增加1
        valid++
      }
    }
    console.log('==1', win, valid, left, right)
    // 当验证数量与需要的字符个数一致时，就应该收缩窗口了
    while (right - left >= t.length) {
      // 在这里判断是否找到了合法的子串
      if (valid === Object.keys(need).length) {
        return true
      }
      //即将移出窗口的字符
      let lc = s[left]
      // 左移窗口
      left++
      console.log('==2', win, valid, left, right)
      if (need[lc]) {
        if (win[lc] == need[lc]) {
          valid--
        }
        win[lc]--
      }
      console.log('==3', win, valid, left, right)
    }
    console.log('==end', win, valid, left, right)
  }
  return false
}
console.log(checkInclusion('ab', 'gbaq'))
// console.log(checkInclusion('ab', 'ab')) // true
// console.log(checkInclusion('ab', 'eidbaooo')) // true
// console.log(checkInclusion('ab', 'eidboaoo')) // false
